/*
 * Copyright (C) 2011 Nicola Bonzanni
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package nl.vu.few.ibivu.jlemon.listgraph;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Set;

import nl.vu.few.ibivu.jlemon.AbstractDigraph;
import nl.vu.few.ibivu.jlemon.IncomingArcIterator;
import nl.vu.few.ibivu.jlemon.OutgoingArcIterator;
import nl.vu.few.ibivu.jlemon.WeakHashSet;
import nl.vu.few.ibivu.jlemon.concepts.AddArcHandler;
import nl.vu.few.ibivu.jlemon.concepts.AddNodeHandler;
import nl.vu.few.ibivu.jlemon.concepts.ClearHandler;
import nl.vu.few.ibivu.jlemon.concepts.EraseArcHandler;
import nl.vu.few.ibivu.jlemon.concepts.EraseNodeHandler;
import nl.vu.few.ibivu.jlemon.concepts.HasAddArcHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasAddNodeHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasClearHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasEraseArcHandlers;
import nl.vu.few.ibivu.jlemon.concepts.HasEraseNodeHandlers;

public class ListDigraph extends AbstractDigraph<Node, ListDigraph.Arc>
		implements HasAddNodeHandlers<Node>, HasEraseNodeHandlers<Node>,
		HasAddArcHandlers<ListDigraph.Arc>,
		HasEraseArcHandlers<ListDigraph.Arc>, HasClearHandlers, Serializable {

	private static final long serialVersionUID = 1L;
	private int arcNum;
	private int nodeNum;

	// FIXME handlers sets are not correctly restored after serialization because WeakHashSet are not serializable
	// since the WeakHashMap they use is not serializable as well
	transient private Set<AddNodeHandler<Node>> addNodeHandlers = new WeakHashSet<AddNodeHandler<Node>>();
	transient private Set<EraseNodeHandler<Node>> eraseNodeHandlers = new WeakHashSet<EraseNodeHandler<Node>>();
	transient private Set<AddArcHandler<Arc>> addArcHandlers = new WeakHashSet<AddArcHandler<Arc>>();
	transient private Set<EraseArcHandler<Arc>> eraseArcHandlers = new WeakHashSet<EraseArcHandler<Arc>>();
	transient private Set<ClearHandler> clearHandlers = new WeakHashSet<ClearHandler>();

	/*
	 * Using integers over pointers lead to save at least 50% of the space on
	 * 64bit JVMs.
	 */
	private int firstFreeArc = -1;
	private int firstFreeNode = -1;
	private int firstNode = -1;

	/*
	 * On one hand, internal structure are needed because we don't want to risk
	 * to remove a node that belongs to another graph. Internal node keep save
	 * the internal list structure of nodes and arcs.
	 * 
	 * On the other hand, we need to keep the reference to the "external" node
	 * object in order to avoid excessive object creation and excessively use
	 * GC.
	 */
	@SuppressWarnings("serial")
	private class InternalNode implements Serializable {
		private Node node = new Node();
		int firstIn = -1;
		int firstOut = -1;
		int previous = -1;
		int next = -1;

		public InternalNode(int id) {
			node.id = id;
		}

		public Node getNode() {
			return node;
		}
	}

	@SuppressWarnings("serial")
	private class InternalArc implements Serializable {
		private Arc arc = new Arc();
		int target = -1;
		int source = -1;
		int previousIn = -1;
		int nextIn = -1;
		int previousOut = -1;
		int nextOut = -1;

		public InternalArc(int id) {
			arc.id = id;
		}

		public Arc getArc() {
			return arc;
		}
	}

	private ArrayList<InternalNode> nodes = new ArrayList<InternalNode>();
	private ArrayList<InternalArc> arcs = new ArrayList<InternalArc>();

	public void ensureNodesCapacity(int minCapacity) {
		nodes.ensureCapacity(minCapacity);
	}
	
	public void ensureArcsCapacity(int minCapacity) {
		arcs.ensureCapacity(minCapacity);
	}
	
	@Override
	public Node source(Arc arc) {
		return nodeFromId(arcs.get(arc.id).source);
	}

	@Override
	public Node target(Arc arc) {
		return nodeFromId(arcs.get(arc.id).target);
	}

	@Override
	public int id(Node node) {
		if (valid(node))
			return node.id;
		return -1;
	}

	@Override
	public int id(Arc arc) {
		if (valid(arc))
			return arc.id;
		return -1;
	}

	@Override
	public Node nodeFromId(int id) {
		if (validNodeId(id))
			return nodes.get(id).getNode();
		return null;
	}

	@Override
	public Arc arcFromId(int id) {
		if (validArcId(id))
			return arcs.get(id).getArc();
		return null;
	}

	@Override
	public int maxNodeId() {
		return nodes.size() - 1;
	}

	@Override
	public int maxArcId() {
		return arcs.size() - 1;
	}

	@Override
	public int nodeNum() {
		return nodeNum;
	}

	@Override
	public int arcNum() {
		return arcNum;
	}

	@Override
	public Node firstNode() {
		return nodeFromId(firstNode);
	}

	@Override
	public Node next(Node node) {
		return nodeFromId((nodes.get(node.id).next));
	}

	@Override
	public Arc firstArc() {
		int n;
		// cycles through all the nodes looking for the first
		// node with an incoming arc
		for (n = firstNode; n != -1 && nodes.get(n).firstIn == -1; n = nodes
				.get(n).next) {
		}
		return (n == -1) ? null : arcFromId(nodes.get(n).firstIn);
	}

	@Override
	public Arc next(Arc arc) {
		if (arcs.get(arc.id).nextIn != -1) {
			return arcFromId(arcs.get(arc.id).nextIn);
		} else {
			int n;
			// starting from the node next to the target of the given arc
			// it cycles through all the nodes looking for the first
			// node with an incoming arc
			for (n = nodes.get(arcs.get(arc.id).target).next; n != -1
					&& nodes.get(n).firstIn == -1; n = nodes.get(n).next) {
			}
			return (n == -1) ? null : arcFromId(nodes.get(n).firstIn);
		}
	}

	@Override
	public Arc firstOut(Node v) {
		return arcFromId(nodes.get(v.id).firstOut);
	}

	@Override
	public Arc nextOut(Arc e) {
		return arcFromId(arcs.get(e.id).nextOut);
	}

	@Override
	public Arc firstIn(Node v) {
		return arcFromId(nodes.get(v.id).firstIn);
	}

	@Override
	public Arc nextIn(Arc e) {
		return arcFromId(arcs.get(e.id).nextIn);
	}

	/**
	 * Return true if the given node is valid, i.e. it is a real node of the
	 * graph. <br>
	 * <br>
	 * <b>Note:</b> A Node pointing to a removed item could become valid again
	 * later if new nodes are added to the graph.
	 * 
	 * @param node
	 * @return true if the given node is valid
	 */
	public boolean valid(Node node) {
		return validNodeId(node.id);
	}

	protected boolean validNodeId(int id) {
		return id >= 0 && id < nodes.size() && nodes.get(id).previous != -2;
	}

	/**
	 * Return true if the given arc is valid, i.e. it is a real arc of the
	 * graph. <br>
	 * <br>
	 * <b>Note:</b> An Arc pointing to a removed item could become valid again
	 * later if new arcs are added to the graph.
	 * 
	 * @param node
	 * @return true if the given node is valid
	 */
	public boolean valid(Arc arc) {
		return validArcId(arc.id);
	}

	protected boolean validArcId(int id) {
		return id >= 0 && id < arcs.size() && arcs.get(id).previousIn != -2;
	}

	/**
	 * Add a new node to the digraph
	 * 
	 * @return the newly created node
	 */
	public Node addNode() {
		int n;
		InternalNode internalNode = null;
		// increase the node count
		nodeNum++;
		// if there is not a free slot, allocate a new slot
		if (firstFreeNode == -1) {
			n = nodes.size();
			internalNode = new InternalNode(n);
			nodes.add(internalNode);
		}
		// if there is a free slot, reuse the object contained in the slot
		else {
			n = firstFreeNode;
			internalNode = nodes.get(n);
			// the next free node is the next node
			firstFreeNode = internalNode.next;
		}
		// the previous first node became the second
		internalNode.next = firstNode;
		if (firstNode != -1) {
			// if there was a previous node in the graph the current node
			// became its previous
			nodes.get(firstNode).previous = n;
		}
		// the current node became the first node
		firstNode = n;
		internalNode.previous = -1;
		// the new node doesn't have any edges
		internalNode.firstOut = internalNode.firstOut = -1;

		Node node = nodeFromId(n);
		for (AddNodeHandler<Node> handler : addNodeHandlers) {
			handler.onAddNode(node);
		}
		return node;
	}

	/**
	 * Add a new arc to the digraph with source node u and target node v
	 * 
	 * @param u
	 *            the source of the new arc
	 * @param v
	 *            the target of the new arc
	 * @return the newly created arc
	 */
	public Arc addArc(Node u, Node v) {
		int n;
		InternalArc a;
		// get the internal data associated with the nodes
		InternalNode internalV = nodes.get(v.id);
		InternalNode internalU = nodes.get(u.id);
		// increase the arcs count
		arcNum++;
		// if there are not free slot for arcs
		if (firstFreeArc == -1) {
			// create new internal structure for the arc
			n = arcs.size();
			a = new InternalArc(n);
			arcs.add(a);
		} else {
			// otherwise reuse a free slot
			n = firstFreeArc;
			a = arcs.get(n);
			// adjourn the first free arc to the next one
			// in the list of free slots
			firstFreeArc = a.nextIn;
		}

		// set source and target for the new arc
		a.source = u.id;
		a.target = v.id;

		// the next outgoing arc of the new arc will be the old first
		// outgoing arc of u (the source node) and the previous outgoing arc
		// of the old first outgoing arc of u, if one already existed,
		// will be the current arc
		a.nextOut = internalU.firstOut;
		if (internalU.firstOut != -1) {
			arcs.get(internalU.firstOut).previousOut = n;
		}

		// the next incoming arc of the new arc will be the old first
		// incoming arc of v (the target node) and the previous incoming arc
		// of the old first incoming arc of v, if one already existed,
		// will be the current arc
		a.nextIn = internalV.firstIn;
		if (internalV.firstIn != -1) {
			arcs.get(internalV.firstIn).previousIn = n;
		}

		// since the newly created arc is the first arc of the list
		// the are no previous incoming or outgoing arcs
		a.previousIn = a.previousOut = -1;

		// set the newly created arc as first outgoing arc of u (the source
		// node) and first incoming arc of v (the target node)
		internalU.firstOut = internalV.firstIn = n;

		Arc arc = arcFromId(n);
		for (AddArcHandler<Arc> handler : addArcHandlers) {
			handler.onAddArc(arc);
		}
		return arc;
	}

	/**
	 * Erase a node from the digraph.
	 * 
	 * @param node
	 *            the node to be erased
	 */
	public void erase(Node node) {
		Arc arc;

		// remove all the outgoing arc
		arc = firstOut(node);
		while (arc != null) {
			erase(arc);
			arc = firstOut(node);
		}

		// remove all the incoming arc
		arc = firstIn(node);
		while (arc != null) {
			erase(arc);
			arc = firstIn(node);
		}

		for (EraseNodeHandler<Node> handler : eraseNodeHandlers) {
			handler.onEraseNode(node);
		}

		// decrease the node count
		nodeNum--;
		// retrieve the internal node data of the node
		InternalNode n = nodes.get(node.id);

		// if the node has a next node, associate the previous of the next node
		// with the previous node
		if (n.next != -1) {
			nodes.get(n.next).previous = n.previous;
		}

		// if the node has a previous node, associate the next of the previous
		// node
		// with the next node
		if (n.previous != -1) {
			nodes.get(n.previous).next = n.next;
		}
		// ..else the next node is the new first node
		else {
			firstNode = n.next;
		}

		// the next node will be the old first free node
		n.next = firstFreeNode;
		// the current node is the head of the list of free nodes
		firstFreeNode = node.id;
		// no need to double link the list of free nodes
		n.previous = -2;
	}

	/**
	 * Erase an arc from the digraph.
	 * 
	 * @param node
	 *            the node to be erased
	 */
	public void erase(Arc arc) {
		InternalArc a = arcs.get(arc.id);

		for (EraseArcHandler<Arc> handler : eraseArcHandlers) {
			handler.onEraseArc(arc);
		}

		// decrease the arcs count
		arcNum--;
		// if the given arc is *not* the last of the incoming arc list,
		// associate the previous inc arc of the next arc with the current
		// previous
		if (a.nextIn != -1) {
			arcs.get(a.nextIn).previousIn = a.previousIn;
		}

		// if the given arc is not the first of the incoming arc list,
		// associate the next inc of the previous inc arc with
		// the current next inc arc
		if (a.previousIn != -1) {
			arcs.get(a.previousIn).nextIn = a.nextIn;
		}
		// if it is the first of the list, associate the first inc arc of
		// the target node to the next node
		else {
			nodes.get(a.target).firstIn = a.nextIn;
		}

		// do the same for the outgoing arcs
		if (a.nextOut != -1) {
			arcs.get(a.nextOut).previousOut = a.previousOut;
		}

		if (a.previousOut != -1) {
			arcs.get(a.previousOut).nextOut = a.nextOut;
		} else {
			nodes.get(a.source).firstOut = a.nextOut;
		}

		a.nextIn = firstFreeArc;
		firstFreeArc = arc.id;
		a.previousIn = -2;
	}

	public void clear() {
		for (ClearHandler handler : clearHandlers) {
			handler.onClear();
		}
		arcNum = nodeNum = 0;
		arcs.clear();
		nodes.clear();
		firstNode = firstFreeNode = firstFreeArc = -1;
	}

	/**
	 * Change the target of the given arc to the given node. <br>
	 * <br>
	 * <b>Note:</b> The <tt>IncomincArcIterator</tt>s and the
	 * <tt>ArcIterator</tt>s referencing the changed arc remain valid. However
	 * the <tt>IncomincArcIterator</tt>s are invalidated.
	 * 
	 * @param arc
	 * @param node
	 *            the new target node
	 */
	public void changeTarget(Arc arc, Node node) {
		InternalArc a = arcs.get(arc.id);
		InternalNode n = nodes.get(node.id);

		if (a.nextIn != -1)
			arcs.get(a.nextIn).previousIn = a.previousIn;
		if (a.previousIn != -1)
			arcs.get(a.previousIn).nextIn = a.nextIn;
		else
			nodes.get(a.target).firstIn = a.nextIn;
		if (n.firstIn != -1) {
			arcs.get(n.firstIn).previousIn = arc.id;
		}
		a.target = node.id;
		a.previousIn = -1;
		a.nextIn = n.firstIn;
		n.firstIn = arc.id;
	}

	/**
	 * Change the source of the given arc to the given node. <br>
	 * <br>
	 * <b>Note:</b> The <tt>IncomincArcIterator</tt>s referencing the changed
	 * arc remain valid. However <tt>ArcIterator</tt>s and
	 * <tt>OutgoingArcIterator</tt>s are invalidated.
	 * 
	 * @param arc
	 * @param node
	 *            the new source node
	 */
	public void changeSource(Arc arc, Node node) {
		InternalArc a = arcs.get(arc.id);
		InternalNode n = nodes.get(node.id);
		if (a.nextOut != -1)
			arcs.get(a.nextOut).previousOut = a.previousOut;
		if (a.previousOut != -1)
			arcs.get(a.previousOut).nextOut = a.nextOut;
		else
			nodes.get(a.source).firstOut = a.nextOut;
		if (n.firstOut != -1) {
			arcs.get(n.firstOut).previousOut = arc.id;
		}
		a.source = node.id;
		a.previousOut = -1;
		a.nextOut = n.firstOut;
		n.firstOut = arc.id;
	}

	/**
	 * Invert the direction of an arc. <br>
	 * <br>
	 * <b>Note:</b> The <tt>ArcIterator</tt>s referencing the changed arc remain
	 * valid. However <tt>OutgoingArcIterator</tt>s and
	 * <tt>IncomincArcIterator</tt>s are invalidated.
	 * 
	 * @param arc
	 *            the arc to invert
	 */
	public void reverseArc(Arc arc) {
		Node t = target(arc);
		changeTarget(arc, source(arc));
		changeSource(arc, t);
	}

	/**
	 * Contracts two nodes. Node b will be removed but instead of deleting its
	 * neighboring arcs, they will be joined to a. Arcs forming loops will be
	 * removed.
	 * 
	 * @param a
	 * @param b
	 * @see #contract(Node, Node, boolean)
	 */
	public void contract(Node a, Node b) {
		contract(a, b, true);
	}

	/**
	 * Contracts two nodes. Node b will be removed but instead of deleting its
	 * neighboring arcs, they will be joined to a.
	 * 
	 * <b>Note:</b>This functionality cannot be used together with the Snapshot
	 * feature.
	 * 
	 * @param a
	 * @param b
	 * @param removeLoops
	 *            if true arcs forming loops will be removed
	 * @see #contract(Node, Node)
	 */
	public void contract(Node a, Node b, boolean removeLoops) {
		OutgoingArcIterator<Arc> o = new OutgoingArcIterator<Arc>(this, b);
		IncomingArcIterator<Arc> i = new IncomingArcIterator<Arc>(this, b);
		// loops through all the arcs outgoing from node b
		while (o.hasNext()) {
			o.next();
			// if the user wants to remove loops and the current arc
			// points to a (the future source node) remove the edge
			if (removeLoops && target(o.peek()).equals(a)) {
				erase(o.peek());
			} else {
				changeSource(o.peek(), a);
			}
		}
		// loops through all the arcs incoming to node b
		while (i.hasNext()) {
			i.next();
			// if the user wants to remove loops and the current arc
			// is coming from a (the future target node) remove the edge
			if (removeLoops && source(i.peek()).equals(a)) {
				erase(i.peek());
			} else {
				changeTarget(i.peek(), a);
			}
		}
		erase(b);
	}

	/**
	 * Split a node. First a new node is added to the digraph, then the source
	 * of each outgoing arc from the give node is moved to this new node. A new
	 * arc from the given node to the newly created node is also added. <br>
	 * <br>
	 * <b>Note:</b> The <tt>ArcIterator</tt>s referencing the changed arc remain
	 * valid. However <tt>OutgoingArcIterator</tt>s and
	 * <tt>IncomincArcIterator</tt>s are invalidated.
	 * 
	 * @param node
	 *            the node to split
	 * @return the newly created node
	 * @see #split(Node, boolean)
	 */
	public Node split(Node node) {
		return split(node, true);
	}

	/**
	 * Split a node. First a new node is added to the digraph, then the source
	 * of each outgoing arc from the give node is moved to this new node. <br>
	 * <br>
	 * <b>Note:</b> The <tt>ArcIterator</tt>s referencing the changed arc remain
	 * valid. However <tt>OutgoingArcIterator</tt>s and
	 * <tt>IncomincArcIterator</tt>s are invalidated.
	 * 
	 * @param node
	 *            the node to split
	 * @param connect
	 *            if true, then a new arc from the given node to the newly
	 *            created node is also added
	 * @return the newly created node
	 * @see #split(Node)
	 */
	public Node split(Node node, boolean connect) {
		OutgoingArcIterator<Arc> o = new OutgoingArcIterator<Arc>(this, node);
		Node b = addNode();
		// loops through all the arcs outgoing from the given node
		while (o.hasNext()) {
			// change the source arc of each outgoing arc to the
			// newly created arc
			changeSource(o.next(), b);
		}
		if (connect)
			addArc(node, b);
		return b;
	}

	/**
	 * Splits an arc. First a new node is added to the digraph, then the
	 * original arc is re-targeted to the newly created node. Finally an arc
	 * from the newly created node is added towards the original target.
	 * 
	 * @param arc
	 * @return the newly created node
	 */
	public Node split(Arc arc) {
		Node b = addNode();
		addArc(b, target(arc));
		changeTarget(arc, b);
		return b;
	}

	@Override
	public Class<Node> getNodeClass() {
		return Node.class;
	}

	@Override
	public Class<Arc> getArcClass() {
		return Arc.class;
	}

	@SuppressWarnings("serial")
	public class Arc implements nl.vu.few.ibivu.jlemon.concepts.Arc,
			Comparable<Arc>, Serializable {
		protected int id = -1;

		@Override
		public int compareTo(Arc arc) {
			if (this.id < arc.id) {
				return -1;
			} else if (this.id > arc.id) {
				return 1;
			}
			return 0;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + getOuterType().hashCode();
			result = prime * result + id;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj) {
				return true;
			}
			if (obj == null) {
				return false;
			}
			if (getClass() != obj.getClass()) {
				return false;
			}
			Arc other = (Arc) obj;
			if (!getOuterType().equals(other.getOuterType())) {
				return false;
			}
			if (id != other.id) {
				return false;
			}
			return true;
		}

		private ListDigraph getOuterType() {
			return ListDigraph.this;
		}
	}

	@Override
	public void addClearHandler(ClearHandler handler) {
		clearHandlers.add(handler);
	}

	@Override
	public void addEraseArcHandler(EraseArcHandler<Arc> handler) {
		eraseArcHandlers.add(handler);
	}

	@Override
	public void addAddArcHandler(AddArcHandler<Arc> handler) {
		addArcHandlers.add(handler);
	}

	@Override
	public void addEraseNodeHandler(EraseNodeHandler<Node> handler) {
		eraseNodeHandlers.add(handler);
	}

	@Override
	public void addAddNodeHandler(AddNodeHandler<Node> handler) {
		addNodeHandlers.add(handler);
	}
}
